package day;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     *
     * @param xianxu  int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve(int[] xianxu, int[] zhongxu) {
        // write code here
        TreeNode root = TreeNode.initTree(xianxu, zhongxu);
        Map<Integer, Integer> map = new HashMap();
        int hight = scan(root, 0, map);
        int[] result = new int[hight];
        for (int i = 0; i < hight; i++) {
            result[i] = map.get(i);
        }
        return result;
    }


    private int scan(TreeNode node, int level, Map<Integer, Integer> map) {
        if (node != null) {
            map.put(level, node.val);
            int left = scan(node.left, level + 1, map);
            int right = scan(node.right, level + 1, map);
            return Math.max(left, right) + 1;
        } else {
            return 0;
        }
    }
}

class TreeNode {
    int val;
    TreeNode left, right;

    static TreeNode initTree(int[] xianxu, int[] zhongxu) {
        if (xianxu.length == 0) {
            return null;
        }
        TreeNode node = new TreeNode();
        node.val = xianxu[0];
        //找到中序的位置
        int idx = 0;
        for (int i = 0; i < zhongxu.length; i++) {
            if (zhongxu[i] == xianxu[0]) {
                idx = i;
                break;
            }
        }
        int[] leftX = Arrays.copyOfRange(xianxu, 1, 1 + idx);
        int[] rightX = Arrays.copyOfRange(xianxu, 1 + idx, xianxu.length);
        int[] leftZ = Arrays.copyOfRange(zhongxu, 0, idx);
        int[] rightZ = Arrays.copyOfRange(zhongxu, idx + 1, zhongxu.length);
        node.left = initTree(leftX, leftZ);
        node.right = initTree(rightX, rightZ);
        return node;
    }

    public static void main(String[] args) {
        int[] xianxu = new int[]{1,2,4,5,3};
        int[] zhongxu = new int[]{4,2,5,1,3};
        int[] solve = new Solution().solve(xianxu, zhongxu);
        System.out.println(solve);
    }
}